package com.lfg.leetcode.leetcode0;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class No40CombinationSum2 {

    public static void main(String[] args) {
        List<List<Integer>> ret = combinationSum2(new int[]{2, 5, 2, 1, 2}, 5);
        System.out.println(ret);
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> set = new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        combinationSum(candidates, new ArrayList<Integer>(), 0, target, set, 0);
        return new ArrayList<>(set);
    }

    public static void combinationSum(int[] candidates, List<Integer> list, int total, int target, List<List<Integer>> set, int index) {
        if (total > target) {
            return;
        } else if (total == target) {
            ArrayList<Integer> l = new ArrayList<>(list);
//            Collections.sort(l);
            set.add(l);
        }
        for (int i = index; i < candidates.length && total + candidates[i] <= target; i++) {
            if (i > index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            list.add(candidates[i]);
            combinationSum(candidates, list, total + candidates[i], target, set, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

